package map_set;

/**
 * @author yuisama
 * @version 1.0.0
 * @Description 基于int开散列方案的哈希表
 * @createTime 2023年04月06日 20:43:00
 */
public class MyHashMap {
    // 定义内部的Node节点
    private static class Node {
        int key;
        int value;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    // 当前哈希表中有效元素个数
    private int size;
    // 取模数,简单起见，和数组长度保持一致
    private int M;
    // 保存Node元素的数组
    private Node[] data;
    // 负载因子
    private static final double LOAD_FACTOR = 0.75;
    public MyHashMap() {
        this(16);
    }
    public MyHashMap(int capacity) {
        this.data = new Node[capacity];
        this.M = capacity;
    }

    // 判断当前哈希表中是否包含指定的key值
    public boolean containsKey(int key) {
        int index = hash(key);
        for (Node x = data[index];x != null;x = x.next) {
            if (x.key == key) {
                return true;
            }
        }
        return false;
    }

    // 判断当前哈希表中是否包含指定的value值
    public boolean containsValue(int value) {
        // 全表扫描
        for (int i = 0; i < data.length; i++) {
            // 内层循环就是每个子链表的遍历
            for (Node x = data[i];x != null;x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 新增 & 修改
     * 在当前哈希表中添加一对新元素，返回添加前的值
     * @param key
     * @param value
     * @return 若新元素，返回-1
     */
    public int put(int key,int value) {
        // 1.首先计算出当前新元素的下标
        int index = hash(key);
        // 2.在当前的子链表中判断key值是否存在，若存在，只需要更新value即可
        for (Node x = data[index];x != null;x = x.next) {
            if (x.key == key) {
                // 存在，只需要更新value
                int oldValue = x.value;
                x.value = value;
                return oldValue;
            }
        }
        // 3.此时key第一次出现，头插到当前的子链表中
        Node node = new Node(key,value);
        node.next = data[index];
        data[index] = node;
        size ++;
        // 4.判断当前哈希表的冲突情况，是否需要扩容
        if (size >= this.data.length * LOAD_FACTOR) {
            resize();
        }
        return -1;
    }

    private void resize() {
        this.M = data.length << 1;
        Node[] newData = new Node[data.length << 1];
        // 搬移原数组的所有节点
        for (int i = 0; i < data.length; i++) {
            for (Node x = data[i];x != null;) {
                Node next = x.next;
                // 当前x搬移到新数组的对应位置
                int newIndex = hash(x.key);
                // 头插到新数组的对应位置
                x.next = newData[newIndex];
                newData[newIndex] = x;
                // 继续搬移原数组的下一个节点
                x = next;
            }
        }
        // 更新data的指向
        data = newData;
    }
    // 在当前哈希表中指定的key值节点
    public boolean removeKey(int key) {
        // 1.先求索引
        int index = hash(key);
        // 先判空
        if(data[index] == null) {
            // 不存在对应的key值
            return false;
        }
        // 剩下就是链表的删除问题
        if (data[index].key == key) {
            data[index] = data[index].next;
            size --;
            return true;
        }
        Node prev = data[index];
        while (prev.next != null) {
            if (prev.next.key == key) {
                prev.next = prev.next.next;
                size --;
                return true;
            }
        }
        // 此时不存在指定的key值
        return false;
    }

    private int hash(int key) {
        return key % this.M;
    }

}
